package avltree;

public class AVLTree {
    //内部类
    static class TreeNode{
        public int val;
        public int bf;//平衡因子
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子
        public TreeNode parent;//父节点

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;//根节点
    public boolean insert(int val){
        TreeNode node=new TreeNode(val);
        if(root==null){
            root=node;
            return true;
        }
        TreeNode parent=null;
        TreeNode cur=root;
        while(cur!=null){
            if(cur.val>val){
                parent=cur;
                cur=cur.left;
            }else if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else{
                return false;
            }
        }
        if(parent.val<val){
            parent.right=node;
        }else{
            parent.left=node;
        }
        node.parent=parent;
        cur=node;
        //平衡因子的修改
        while(parent!=null){
            //先看cur是parent的左还是右，决定平衡因子是++还是--
            if(cur==parent.right){
                //如果是右树，则右树高度增加，平衡因子++
                parent.bf++;
            }else{
                //如果是左树，则左树高度增加，平衡因子--
                parent.bf--;
            }
            //检查当前平衡因子 0 1 -1
            if(parent.bf==0){
                //说明已经平衡了
                break;
            }else if(parent.bf==1||parent.bf==-1) {
                //还需要向上检查判断
                cur=parent;
                parent=cur.parent;
            }else{
                if(parent.bf==2){//说明右树高 需要降低右树的高度
                    if(cur.bf==1){
                        //左旋
                        rotateLeft(parent);
                    }else{//cur.bf==-1
                        //左右双旋
                        rotateRL(parent);
                    }
                }else{//parent.bf==-2 说明左树高 需要降低左树的高度
                    if(cur.bf==-1){
                        //右旋
                        rotateRight(parent);
                    }else{
                        //右左双旋
                        rotateLR(parent);
                    }
                }
                //此时已经平衡了
                break;
            }
        }
        return true;
    }

    //右左双旋
    private void rotateRL(TreeNode parent) {
        TreeNode subR=parent.right;
        TreeNode subRL=subR.left;
        int bf=subRL.bf;

        rotateRight(parent.right);
        rotateLeft(parent);

        if(bf==1){
            parent.bf=-1;
            subR.bf=0;
            subRL.bf=0;
        }else if(bf==-1){
            parent.bf=0;
            subR.bf=1;
            subRL.bf=0;
        }
    }

    //左右双旋
    private void rotateLR(TreeNode parent) {
        TreeNode subL=parent.left;
        TreeNode subLR=subL.right;
        int bf=subLR.bf;

        rotateLeft(parent.left);
        rotateRight(parent);

        if(bf==-1){
            subL.bf=0;
            subLR.bf=0;
            parent.bf=1;
        }else if(bf==1){
            subL.bf=-1;
            subLR.bf=0;
            parent.bf=0;
        }
    }

    //左旋
    private void rotateLeft(TreeNode parent) {
        //先定义subL、subR的位置
        TreeNode subR=parent.right;
        TreeNode subRL=subR.left;
        //旋转
        parent.right=subRL;
        subR.left=parent;
        if(subRL!=null){
            subRL.parent=parent;
        }
        TreeNode pParent=parent.parent;
        parent.parent=subR;

        //检查当前节点是不是根节点
        if(parent==root){
            root=subR;
            root.parent=null;
        }else{
            //不是根节点 判断是左子树还是右子树
            if(parent==pParent.left){
                pParent.left=subR;
            }else{
                pParent.right=subR;
            }
            subR.parent=pParent;
        }
        subR.bf=0;
        parent.bf=0;
    }

    //右旋
    private void rotateRight(TreeNode parent) {
        //先定义subL、subR的位置
        TreeNode subL=parent.left;
        TreeNode subLR=subL.right;
        //旋转
        parent.left=subLR;
        subL.right=parent;
        if(subLR!=null){
            subLR.parent=parent;
        }
        TreeNode pParent=parent.parent;
        parent.parent=subL;

        //检查当前节点是不是根节点
        if(parent==root){
            root=subL;
            root.parent=null;
        }else{
            //不是根节点 判断是左子树还是右子树
            if(pParent.left==parent){
                pParent.left=subL;
            }else{
                pParent.right=subL;
            }
            subL.parent=pParent;
        }
        subL.bf=0;
        parent.bf=0;
    }
    public void inorder(TreeNode root){
        if(root == null) return;
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }
    private int height(TreeNode root) {
        if(root == null) return 0;
        int leftH=height(root.left);
        int rightH=height(root.right);
        return leftH>rightH ? leftH+1 : rightH+1 ;
    }
    public boolean isBalance(TreeNode root) {
        if(root == null) return true;
        int leftH = height(root.left);
        int rightH = height(root.right);
        //检查平衡因子
        if(rightH - leftH != root.bf) {
            System.out.println(root.val+" 平衡因子异常！");
            return false;
        }
        return Math.abs(leftH-rightH) <= 1 &&isBalance(root.left) && isBalance(root.right);
    }

}
